package com.algorithm.bubble;/*
 *@Author:DOWN
 *@Date:2022/3/15 14:42
 *@Comment:冒泡排序
 */

public class BubbleReversedSort {
    private BubbleReversedSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {

        for (int i = 0; i + 1 < data.length; i++) {

            // arr[0, i) 已排好序
            // 通过冒泡在 arr[i] 位置放上合适的元素
            for (int j = data.length - 1; j > i; j--) {
                if (data[j - 1].compareTo(data[j]) > 0) {
                    swap(data, j - 1, j);
                }
            }
        }
    }

    /**
     * 优化 检测是否是可以提前结束排序
     *
     * @param data 元素组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void sort2(E[] data) {

        for (int i = 0; i + 1 < data.length; i++) {

            // arr[0, i) 已排好序
            // 通过冒泡在 arr[i] 位置放上合适的元素
            boolean isSwapped = false;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j - 1].compareTo(data[j]) > 0) {
                    swap(data, j - 1, j);
                    isSwapped = true;
                }
            }

            if (!isSwapped) {
                break;
            }
        }
    }

    /**
     * 优化2 直接跳过有序区间
     *
     * @param data 元素组
     * @param <E> 泛型
     */
    public static <E extends Comparable<E>> void sort3(E[] data) {

        for (int i = 0; i + 1 < data.length; ) {

            // arr[0, i) 已排好序
            // 通过冒泡在 arr[i] 位置放上合适的元素
            int lastSwappedIndex = data.length - 1;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j - 1].compareTo(data[j]) > 0) {
                    swap(data, j - 1, j);
                    lastSwappedIndex = j - 1;
                }
            }

            i = lastSwappedIndex + 1;
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
